/*
 * @Author: liusheng
 * @Date: 2022-08-07 22:21:36
 * @LastEditors: liusheng
 * @LastEditTime: 2022-08-07 22:27:35
 * @Description: 剑指 Offer II 102. 加减的目标值
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 102. 加减的目标值
给定一个正整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

 

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：

输入：nums = [1], target = 1
输出：1
 

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
 

注意：本题与主站 494 题相同： https://leetcode-cn.com/problems/target-sum/

通过次数12,422  提交次数21,826
 */

#include "header.h"

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        int n = nums.size();

        for (auto num : nums)
        {
            sum += num;
        }

        /*
        positive = sum - negative
        (sum - negative) - negative = sum - 2 * negative = target
        negative = (sum - target) / 2
        */

        int diff = sum - target;
        if (diff < 0 || diff % 2)
        {
            return 0;
        }

        int negative = diff / 2;

        /*
        dp[i][j] means select sum(j) from 0 to ith
        */
        vector<vector<int>> dp(n + 1,vector<int>(negative + 1, 0));
        dp[0][0] = 1;

        for (int i = 1; i <= n; ++i)
        {
            int num = nums[i-1];
            for (int j = 0; j <= negative; ++j)
            {
                dp[i][j] = dp[i-1][j];
                if (j >= num)
                {
                    dp[i][j] += dp[i-1][j-num];
                }
            }
        }

        return dp[n][negative];
    }
};

/*
same as above,use scroll array to optimize the memory usage
*/
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        int n = nums.size();

        for (auto num : nums)
        {
            sum += num;
        }

        /*
        positive = sum - negative
        (sum - negative) - negative = sum - 2 * negative = target
        negative = (sum - target) / 2
        */

        int diff = sum - target;
        if (diff < 0 || diff % 2)
        {
            return 0;
        }

        int negative = diff / 2;

        /*
        scroll array optimize
        */
        vector<int> dp(negative + 1, 0);
        dp[0] = 1;

        for (int i = 1; i <= n; ++i)
        {
            int num = nums[i-1];
            for (int j = negative; j >= num; --j)
            {
                dp[j] += dp[j-num];
            }
        }

        return dp[negative];
    }
};
